package trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Vector;

public class RadixTree implements Tree<String> {

	private RadixTreeNode root;

	public RadixTree() {
		root = new RadixTreeNode("");
	}
	
	@Override
	public int depth() {
		ArrayList<RadixTreeNode> list = new ArrayList<RadixTreeNode>();
		ArrayList<RadixTreeNode> nextList;
		list.add(root);
		int depth = -1;
		while(!list.isEmpty()) {
			nextList = new ArrayList<RadixTreeNode>();
			depth ++;
			for(RadixTreeNode node : list) {
				for (RadixTreeNode child : node.children)
					nextList.add(child);
			}
			list = nextList;
		}

		return depth;
	}

	@Override
	public void insert(String element) {
		root.insert(element);
	}

	@Override
	public Iterable iterator() {
		LinkedList<String> iterator;
		iterator = new LinkedList<String>();
		root.gatherStrings(iterator, "");
		return iterator;
	}

	@Override
	public String remove(String element) {
		if (root.remove(element))
			return element;
		return null;
	}

	@Override
	public int size() {
		return root.descendantCount();
	}
	
	public boolean contains(String string) {
		return root.contains(string);
	}
	
	public String toString() {
		return root.toString(0);
	}

	private static String longestMatchingPrefix(String strA, String strB) {
		String output = "";
		for (int i = 0; i < strA.length() && i < strB.length(); i ++)
			if (strA.charAt(i) == strB.charAt(i))
				output += strA.charAt(i);
			else 
				break;
		return output;
	}
	
	private class RadixTreeNode {
		private String subString;
		private Vector<RadixTreeNode> children;
		private boolean validString;

		private RadixTreeNode(String aSubString) {
			this(aSubString, false);
		}
		
		private RadixTreeNode(String aSubString, boolean aValidString) {
			subString = aSubString;
			children = new Vector<RadixTreeNode>();
			validString = aValidString;
		}

		/** */
		private void insert(String toInsert) {
			RadixTreeNode n;
			Vector<RadixTreeNode> c;
			String nextStr;

			/* must split this node since arg is a substring */
			if (subString.startsWith(toInsert) && !subString.equals(toInsert)) { //TODO check != req.
				n = new RadixTreeNode(subString.replaceFirst(toInsert, ""));
				c = n.children;
				n.children = children;
				children = c;
				children.add(n);
				subString = toInsert;
				n.validString = validString;
				validString = true;
				return;
			}
			/* must cut arg and insert */
			else if (toInsert.startsWith(subString)) {
				nextStr = toInsert.replaceFirst(subString, "");
				for (RadixTreeNode child : children) {
					if (nextStr.length() > 0 && child.subString.startsWith("" +nextStr.charAt(0))) {
						child.insert(nextStr);
						return;
					}
				}
				children.add(new RadixTreeNode(nextStr, true));
			} else {
				nextStr = longestMatchingPrefix(subString, toInsert);

				/* set up child representing this substring state */
				n = new RadixTreeNode(subString.replaceFirst(nextStr, ""));
				c = n.children;
				n.children = children;
				children = c;
				children.add(n);
				n.validString = validString;
				validString = false;
				subString = nextStr;

				/* set up child representing inserted string state */
				n = new RadixTreeNode(toInsert.replaceFirst(nextStr, ""));
				children.add(n);
				n.validString = true;

				return;
			}
		}
		
		private boolean contains(String str) {
			String nextStr;
			if (subString.equals(str) && validString) {
				return true;
			} else if (str.startsWith(subString)) {
				nextStr = str.replaceFirst(subString, "");
				for (RadixTreeNode child : children)
					if (child.contains(nextStr))
						return true;
			}
			return false;
		}

		private boolean remove(String toRemove) {
			String matchPrefix;
			for (RadixTreeNode child : children) {
				/* if node is the end of the string to be removed */
				if (child.subString.equals(toRemove) && child.validString) {
					child.validString = false;
					/* if node can be pruned */
					if (child.children.size() == 0)
						children.remove(child);
					return true;
				}
				/* if node is not the end */
				else if ((matchPrefix = longestMatchingPrefix(toRemove, child.subString)).length() != 0) {
					return child.remove(toRemove.replaceFirst(matchPrefix, ""));
				}
			}
			return false;
		}
		
		private void gatherStrings(LinkedList<String> list, String prefix) {
			if (validString)
				list.add(prefix + subString);
			for (RadixTreeNode child : children)
				child.gatherStrings(list, prefix + subString);
		}
		
		private int descendantCount() {
			int count = 0;
			for (RadixTreeNode child : children) {
				if (child.validString)
					count += 1;
				count += child.descendantCount();
			}
			return count;
		}
		
		private String toString(int depth) {
			String output = "";
			for (int i = 0; i < depth; i ++)
				output += "\t";
			output += subString + '\n';
			for (RadixTreeNode child : children)
				output += child.toString(depth + 1);
			return output;
		}
	}
}
